package com.ting.test.algorithms.strings;

/**
 * Created by 雷霆 on 2021/1/14.
 * <p>
 * Description：给定一个整型数组arr，代表数值不同的纸牌排成一条线，
 * 玩家A和玩家B依次拿走每张纸牌，
 * 规定玩家A先拿，玩家B后拿，
 * 但是每个玩家每次只能拿走最左或最右的纸牌，
 * 玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数。
 */
public class FaPai {

    public static void main(String[] args) {
        int[] arr = { 5, 7, 4, 5, 8, 1, 6, 0, 3, 4, 6, 1, 7 };
        System.out.println(win1(arr));
    }


    // 根据规则，返回获胜者的分数
    public static int win1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int first = f(arr, 0, arr.length - 1);
        int second = s(arr, 0, arr.length - 1);
        return Math.max(first, second);
    }


    /**
     * 先手的取牌函数
     *
     * @param arr
     * @param L
     * @param R
     * @return
     */
    public static int f(int[] arr, int L, int R) {
        //对于先手而言，如果只有一张牌，则这张牌肯定是属于先手

        if (L == R) {
            return arr[R];
        }

        // 这种情况属于异常，做异常处理
        if (L > R) {
            return -1;
        }

        //对于先手而言，则获得的牌的策略是 第一次（先手）获取的牌+第二次（后手）获取的牌 最大
        // 可以有两种取牌的方法
        //第一种方法，第一次取牌时，作为先手取L位置的牌，则下一次取牌时，取牌的范围是L+1,R,且先手作为后手取牌，
        int firstWay = arr[L] + s(arr, L + 1, R);
        //第而种方法，第一次取牌时，作为先手取R位置的牌，则下一次取牌时，取牌的范围是L,R-1,且先手作为后手取牌，
        int secondWay = arr[R] + s(arr, L, R - 1);

        //对于先手而言，肯定是希望能够自己拿到最大的牌，同时后手拿到小牌，
        // 因此此处返回二者的最大值
        return Math.max(firstWay, secondWay);

    }


    /**
     * 后手的取牌函数
     *
     * @param arr
     * @param L
     * @param R
     * @return
     */
    public static int s(int[] arr, int L, int R) {
        //对于后手而言，如果只有一张牌，则这张牌肯定是属于先手，后手拿不到牌
        if (L == R) {
            return 0;
        }
        // 这种情况属于异常，做异常处理
        if (L > R) {
            return -1;
        }
        //对于后而言，取牌的策略要根据先手的取牌策略而定， 可以有两种取牌的方法
        //第一种，如果先手取L位置的牌，则后手作为先手取牌的范围是L+1,R 且L位置的牌肯定不是后手的
        int firstWay = f(arr, L + 1, R);
        //第二种，如果先手取R位置的牌，则后手作为先手取牌的范围是L,R-1
        int secondWay = f(arr, L, R - 1);
        //此处返回最小值的原因是，先手是足够聪明的，肯定不会让后手拿到大牌，
        // 因此，会想尽办法让后手拿到最小的牌
        return Math.min(firstWay, secondWay);
    }

}
